package Algorithm.Search;

/**
 * 二分查找法
 * @author chenjunjie
 * @since 2018-04-17
 */
public class DichotomySearch {
    public static void main(String[] args) throws Exception {
        // 二分法之前首先要保证数组是有序的
        int[] arr = new int[] { 12, 23, 34, 45, 56, 67, 77, 89, 90, 97, 100 };
        System.out.printf("position: %d\n",search(arr, 0, arr.length-1, 34));
        System.out.printf("position--->: %d\n",search(arr, 45));


    }

    /**
     *  二分法查找某个值(递归)
     * @param arr   原始数组
     * @param begin 索引起始位置
     * @param end   索引结束位置
     * @param key   要查找的值
     * @return 返回查到的值所在的索引
     */
    public static int search(int[] arr, int begin, int end, int key) throws Exception {
        if(key >= arr[begin] && key <= arr[end] ) {
            int point = begin + ((end - begin) >> 1);

            if (begin == point) {
                throw new Exception("没找到这条数据");
            }
            if (key == arr[point]) {
                return point;
            } else if (key > arr[point]) {
                begin = point;
                return search(arr, begin, end, key);
            } else {
                end = point;
                return search(arr, begin, end, key);
            }
        }

        throw new Exception("注意排序，没找到这条数据");
    }

    /**
     * 二分法查找某个值(非递归)
     * @param arr 原始数组
     * @param key 要查找的值
     * @return 返回查到的值所在的索引
     */
    public static int search(int[] arr, int key) throws Exception {
        int begin = 0;
        int end = arr.length;
        int point = begin + ((end - begin) >> 1);
        while(begin < point && end > point){
            if (key == arr[point]) {
                return point;
            }
            if (key > arr[point]) {
                begin = point;
            }else {
                end = point;
            }
            point = begin + ((end - begin) >> 1);
            if (begin == point) {
                throw new Exception("没找到这条数据");
            }
        }

        throw new Exception("注意排序，没找到这条数据");
    }


}
